366. Find Leaves of Binary Tree
Medium

Given the root of a binary tree, collect a tree's nodes as if you were doing this:

  • Collect all the leaf nodes.
  • Remove all the leaf nodes.
  • Repeat until the tree is empty.

 

Example 1:

Input: root = [1,2,3,4,5]
Output: [[4,5,3],[2],[1]]
Explanation:
[[3,5,4],[2],[1]] and [[3,4,5],[2],[1]] are also considered correct answers since per each level it does not matter the order on which elements are returned.

Example 2:

Input: root = [1]
Output: [[1]]

 

Constraints:

  • The number of nodes in the tree is in the range [1, 100].
  • -100 <= Node.val <= 100
Accepted
90.2K
Submissions
124K
Seen this question in a real interview before?
Companies

Average Rating: 5.00 (9 votes)

Premium

Approach 1: DFS (Depth-First Search) with sorting

Intuition

The order in which the elements (nodes) will be collected in the final answer depends on the "height" of these nodes. The height of a node is the number of edges from the node to the deepest leaf. The nodes that are located in the ith height will be appear in the ith collection in the final answer. For any given node in the binary tree, the height is obtained by adding 1 to the maximum height of any children. Formally, for a given node of the binary tree root\text{root}, it's height can be represented as

height(root)=1+max(height(root.left), height(root.right)) \text{height(root)} = \text{1} + \text{max(height(root.left), height(root.right))}

Where root.left\text{root.left} and root.right\text{root.right} are left and right children of the root respectively

Algorithm

In our first approach, we'll simply traverse the tree recursively in a depth first search manner using the function int getHeight(node), which will return the height of the given node in the binary tree. Since height of any node depends on the height of it's children node, hence we traverse the tree in a post-order manner (i.e. height of the childrens are calculated first before calculating the height of the given node). Additionally, whenever we encounter a null node, we simply return -1 as it's height.

Next, we'll store the pair (height, val) for all the nodes which will be sorted later to obtain the final answer. The sorting will be done in increasing order considering the height first and then the val. Hence we'll obtain all the pairs in the increasing order of their height in the given binary tree.

Attached below is the video which shows the calculation of height in a height-first-search manner for the binary tree given in the example.

Below is the implementaion of this approach

Complexity Analysis

  • Time Complexity: Assuming NN is the total number of nodes in the binary tree, traversing the tree takes O(N)O(N) time. Sorting all the pairs based on their height takes O(NlogN)O(N \log N) time. Hence overall time complexity of this approach is O(NlogN)O(N \log N)

  • Space Complexity: O(NlogN)O(N \log N), the space used by pairs and solution.


Approach 2: DFS (Depth-First Search) without sorting

We've seen in approach 1 that there is an additional sorting that is being performed, which increases the overall time complexity to O(NlogN)O(N \log N). The question we can ask here is, can we do better than this? To answer this, we try to remove the sorting by directly placing all the values in their respective positions, i.e. instead of using the pairs array to collect all the (height, val) pairs and then sorting them based on their heights, we'll directly obtain the solution by placing each element (val) to its correct position in the solution array. To clarify, in the given binary tree, [4, 3, 5] goes into the first position, [2] goes into the second position and [1] goes into the third position in the solution array.

To do this, we modify our getHeight method to directly insert the node's value in the solution array at the correct location. Solution array is kept empty in the beginning and as we encounter elements with increasing height, we'll keep increasing the size of the solution array to accomodate for these elements. For example, if our solution array currently is [[4, 3, 5]] and if we want to insert 2 at the second position, we first create the space for 2 by increasing the size of the solution array by 1 and then insert 2 at it's correct location.

  • [[4, 3, 5]] -> [[4, 3, 5], []] # increase the size of solution array

  • [[4, 3, 5], []] -> [[4, 3, 5], [2]] # insert 2 at it's correct location

Below is the implementation of the above mentioned approach.

Complexity Analysis

  • Time Complexity: Assuming NN is the total number of nodes in the binary tree, traversing the tree takes O(N)O(N) time and storing all the pairs at the correct position also takes O(N)O(N) time. Hence overall time complexity of this approach is O(N)O(N).

  • Space Complexity: O(N)O(N), the space used by solution array.

Report Article Issue

Comments: 12
jz2966's avatar
Read More

Here's a simple python DFS implementation used to populate a dictionary (key = index, values = list of nodes), O(N) space, O(N) time, beats 99%

The DFS recursively calculates the layer index by getting the maximum depth from the left and right subtrees of a given node, which is then used to populate the dictionary.

def findLeaves(self, root: TreeNode) -> List[List[int]]:
    output = collections.defaultdict(list)
    
    def dfs(node, layer):
        if not node: 
            return layer 
        left = dfs(node.left, layer)
        right = dfs(node.right, layer)
        layer = max(left, right)
        output[layer].append(node.val)
        return layer + 1
    
    dfs(root, 0)
    return output.values() 

9
Show 1 reply
Reply
Share
Report
AshVis's avatar
Read More

is it necessary to not remove the nodes from root passed in ?

2
Show 1 reply
Reply
Share
Report
saneeshjose's avatar
Read More

Relatively concise answer:

class Solution {
    public List<List<Integer>> findLeaves(TreeNode root) {
        List<List<Integer>> leaves = new ArrayList<>();
        findLeaves(root, leaves);
        return leaves;
    }
    
    public int findLeaves(TreeNode n, List<List<Integer>> leaves) {
        if(n == null) return 0;
        int dOrder = 1+ Math.max(findLeaves(n.left, leaves), findLeaves(n.right, leaves));
        if(dOrder != 0) {
            if(leaves.size() == dOrder - 1) leaves.add(new ArrayList<Integer>());
            leaves.get(dOrder-1).add(n.val);
        }
        return dOrder;
    }
}

1
Show 2 replies
Reply
Share
Report
asheesh2's avatar
Read More

I found removing leaf nodes in every iteration very intuitive.

I have solved the problem in following way

  1. do postorder traversal
  2. add the node to the sublist if it is a leaf node.
  3. remove the node from the tree if it is a leaf
  4. add sublist to final answer

It performs in 0ms and memory better than 99.87%.

    List> ans = new ArrayList<>();
    public List> findLeaves(TreeNode root) {
        if(root == null) return ans;
        while(true) {
            List subAns = new ArrayList();
            if(postorder(root, subAns) == 1){
                ans.add(subAns);
                break;
            }
            ans.add(subAns);
        }
        return ans;
    }
    
    int postorder(TreeNode root, List subAns) {
        if(root == null) return 0;
        int left = postorder(root.left, subAns);
        int right = postorder(root.right, subAns);
        if(root.left == null && root.right == null) {
            subAns.add(root.val);
            return 1;
        }
        if(left == 1) {
            root.left = null;
        }
        if(right == 1) {
            root.right = null;
        }
        return 0;
    }
}

1
Show 1 reply
Reply
Share
Report
shine1691's avatar
Read More

My O(n) solution using hashMap

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    
    Map<Integer, List<Integer>> nodeMap = new HashMap<>();
    
   public List<List<Integer>> findLeaves(TreeNode root) {
        nodeByHeight(root);
        List<List<Integer>> ans = new ArrayList<>();
        int key = 0;
       while(nodeMap.containsKey(key)) {
           ans.add(nodeMap.get(key++));
       }
       
       return ans;
    }
    
    private int nodeByHeight(TreeNode root) {
        if (root == null) return -1;
        int left = nodeByHeight(root.left);
        int right = nodeByHeight(root.right);
        
        int height = Math.max(left, right) + 1;
        
        List<Integer> arrList = new ArrayList<>();
        if (nodeMap.containsKey(height)) {
            arrList = nodeMap.get(height);
        }
        arrList.add(root.val);
        nodeMap.put(height, arrList);
        return height;
    }
}

1
Show 1 reply
Reply
Share
Report
john_winniethepooh's avatar
Read More

Am I seriously the first comment?

1
Show 1 reply
Reply
Share
Report
satinMango's avatar
Read More

class Solution {
    public List<List<Integer>> findLeaves(TreeNode root) {
    
        List<List<Integer>> res = new ArrayList<>();
        while(!isLeaf(root)) {
            List<Integer> picked = new ArrayList();
            extractLeaves(root, picked);
            res.add(picked);
        }
        res.add(Collections.singletonList(root.val));
        return res;
    }
    
    private void extractLeaves(TreeNode root, List<Integer> picked) {
        if(!isLeaf(root)) {
            if(isLeaf(root.left)) {
                // pick root.left
                picked.add(root.left.val);
                // root.left as null
                root.left = null;
            }
            
            if(isLeaf(root.right)) {
                //
                picked.add(root.right.val);
                root.right = null;
            }
            if(root.right != null)
                extractLeaves(root.right, picked);
            if(root.left != null)
                extractLeaves(root.left, picked);
        }
    }
    
    private boolean isLeaf(TreeNode node) {
        if(node != null) {
            return node.left == null && node.right == null;    
        }
        return false;
    }
}

0
Reply
Share
Report
purvasingh2906's avatar
Read More

Why are we returning -1 as the height for leaf nodes? Actually, I tried the same code but I returned 0 as height of leaf node instead of -1. The code failed with the following error: applying non-zero offset 24 to null pointer.

0
Show 1 reply
Reply
Share
Report
user5478G's avatar
Read More

class Solution {
public List<List> findLeaves(TreeNode root) {

    List<List<Integer>> output = new ArrayList();
    TreeNode tempRoot = root;
    while(tempRoot != null && (tempRoot.left != null || tempRoot.right != null)){
        List<Integer> leaves = new ArrayList();
        collectLeaves(leaves, tempRoot, null, null);
        output.add(leaves);
        
    }
    
    List<Integer> rootLevel = new ArrayList();
    rootLevel.add(tempRoot.val);
    output.add(rootLevel);
    
    return output;
}

public void collectLeaves(List<Integer> leaves, TreeNode root, TreeNode parent, Boolean leftChild){
    if(root == null) return;
    
    if(root.left == null && root.right == null){
        leaves.add(root.val);
        if(parent != null){
            if(leftChild){
                parent.left = null;
            }else{
                parent.right = null;
            }
        }else{
           root = null;

        }
    }else{
        collectLeaves(leaves, root.left, root, true);
        collectLeaves(leaves, root.right, root, false);
    }
    
    
    
}

0
Show 1 reply
Reply
Share
Report
abhishekshori's avatar
Read More

Swift solution, > 90%

private func find(_ root: TreeNode?, _ ans: inout [[Int]]) -> Int {
        if root == nil {return 0}
        let h = 1 + max(find(root?.left, &ans), find(root?.right, &ans))        
        if !ans.indices.contains(h-1) {
            let nodes = [Int]()
            ans.append(nodes)
        }
        if let node = root {
            ans[h-1].append(node.val)
        }
        return h
    }
    
    func findLeaves(_ root: TreeNode?) -> [[Int]] {
        if root == nil {return []}
        var ans = [[Int]]()
        find(root, &ans)
        return ans
    }

0
Reply
Share
Report

You don't have any submissions yet.

/23
Contribute
|||
Saved
Trie
#208 Implement Trie (Prefix Tree)
Medium
#211 Design Add and Search Words Data Structure
Medium
#212 Word Search II
Hard
#336 Palindrome Pairs
Hard
#421 Maximum XOR of Two Numbers in an Array
Medium
#425 Word Squares
Hard
#472 Concatenated Words
Hard
#642 Design Search Autocomplete System
Hard
#648 Replace Words
Medium
#676 Implement Magic Dictionary
Medium
#677 Map Sum Pairs
Medium
#692 Top K Frequent Words
Medium
#720 Longest Word in Dictionary
Easy
#745 Prefix and Suffix Search
Hard
#1023 Camelcase Matching
Medium
#1032 Stream of Characters
Hard
#1065 Index Pairs of a String
Easy
#1638 Count Substrings That Differ by One Character
Medium
#1698 Number of Distinct Substrings in a String
Medium
#1707 Maximum XOR With an Element From Array
Hard
#1803 Count Pairs With XOR in a Range
Hard
#1804 Implement Trie II (Prefix Tree)
Medium
#1858 Longest Word With All Prefixes
Medium